# 给定一个可包含重复数字的序列 nums ，按任意顺序 返回所有不重复的全排列。
#
#  示例 1：
# 输入：nums = [1,1,2]
# 输出：
# [[1,1,2], [1,2,1], [2,1,1]]
#
#  示例 2：
# 输入：nums = [1,2,3]
# 输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
from typing import List


class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        """
         重复的本质是，多次选择了值相同的元素。而相同的值对于排序来说是一样的
         去重思路：
         举个栗子，对于两个相同的数1, 1，分别将其命名为1a, 1b(1a表示第一个1，1b表示第二个1)；
         那么，不做去重的话，会有两种重复排列 1a,1b ; 1b,1a， 不要重复的我们只需要取其中任意一种排列；
         为了达到这个目的，限制一下1a, 1b访问顺序即可。 比如只取1a1b那个排列的话，只有当访问了 nums[i-1]之后我们才去访问 nums[i]，
         也就是如果!visited[i-1]的话则continue
        :param nums:
        :return:
        """
        res = []
        nums.sort()  # 排序后所有重复的元素都会相邻，就方便限制相邻的重复数字的访问顺序

        def backTrack(visited: List[bool], singleRes: List[int]) -> None:
            if len(singleRes) == len(nums):
                res.append(list(singleRes))
            for i, num in enumerate(nums):
                if i > 0 and nums[i] == nums[i - 1] and not visited[i - 1]:  # 限制两个相邻的重复数字的访问顺序
                    continue
                if not visited[i]:
                    singleRes.append(num)
                    visited[i] = True
                    backTrack(visited, singleRes)
                    visited[i] = False
                    singleRes.pop()

        backTrack([False] * len(nums), [])
        return res


if __name__ == "__main__":
    nums = [2, 1, 1, 2]
    # nums2 = [1, 1, 2]
    # print(id(nums) == id(nums2))
    print(Solution().permuteUnique(nums))
